#include <iostream>
using namespace std;

int const maxn = 1000007;
int const mo = 1000000000;
int f[maxn];
int n;

int main()
{
	cin >> n;
	f[0] = 1;
	for (int i = 0; i <= n; i++) {
		if (!(i&1)) {
			f[i+2] = (f[i+2] + f[i]) % mo;
			f[i+1] = (f[i+1] + f[i]) % mo;
		}
		if (i*2 <= n) f[i*2] = (f[i*2] + f[i]) % mo;
	}
	cout << f[n] << endl;
}
